package 图.岛屿问题;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/7/8 19:49
 */
public class lc200岛屿问题 {

    /*
     毫无疑问这道题,是非常经典的 DFS , BFS, 并查集 练习题


     - 淹没法
     - 感染法
     */



    //用 BFS 来实现一下!

    /*
    下面这句话 去理解一下:
     不少同学用广搜做这道题目的时候，超时了。 这里有一个广搜中很重要的细节：

    根本原因是只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过。

    很多同学可能感觉这有区别吗？

    如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。
     */
    int direction[][] = {{1,0},{0,1},{-1,0},{0,-1}};

    public int solve(int martix[][]){
        int ans = 0;
        for(int i = 0;i< martix.length;i++){
            for(int j = 0;j < martix[0].length;j++){
                if(martix[i][j] != 0){
                    ans++;
                    bfs(martix,i,j);
                }
            }
        }
        return ans;
    }

    public void bfs(int martix[][],int i,int j){

        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{i,j});
        martix[i][j] = 0;
        while(!queue.isEmpty()){
            int[] remove = queue.remove();
//            martix[remove[0]][remove[1]] = 0;  // 感染掉
            for(int dir[] : direction){
                int _x = dir[0] + remove[0];
                int _y = dir[1] + remove[1];
                if(  _x < 0 || _y < 0 || _x == martix.length || _y == martix[0].length  || martix[_x][_y] == 0){
                    continue;
                }
                queue.addLast(new int[]{_x,_y});
                martix[_x][_y] = 0;
            }
        }
    }


}
